package com.simonf.dynamic_programing;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: smionf
 * @Date: 2024/02/21/15:09
 * @Description:
 */
public class LC53MaxSubArray {
    public int maxSubArray(int[] nums) {

        //dp为子数和
        int[] dp = new int[nums.length];

        if(nums.length == 1){
            dp[0] = nums[0];
            return dp[0];
        }

        //dp[i] = max(nums[i],dp[i-1]+nums[i])

        int max = Math.max(nums[0], nums[1]);
        for(int i=1;i<nums.length;i++)
        {
            dp[0] = nums[0];
            dp[i] = Math.max(nums[i],dp[i-1]+nums[i]);
            max = Math.max(max, dp[i]);
        }
        return max;

    }
}
